import cgi
import os
import logging
import base64

from collections import deque
from xml.etree import ElementTree as ET
from google.appengine.ext.webapp import template
from models import model
from google.appengine.ext import webapp
from google.appengine.ext.webapp.util import run_wsgi_app
from google.appengine.ext import db

class Game(webapp.RequestHandler):
    
    board = [[6,6,6,6,6,6,6,6,6,6,6],[6,2,2,2,2,2,0,0,0,0,6],[6,2,0,4,4,2,0,0,0,0,6],[6,2,2,2,2,2,0,0,0,0,6],[6,0,0,0,0,0,0,0,0,0,6],[6,0,0,0,0,0,0,0,0,0,6],[6,0,0,0,0,0,0,0,0,0,6],[6,0,0,0,0,0,0,0,0,0,6],[6,0,0,0,0,0,0,0,0,0,6],[6,0,0,0,0,0,0,0,0,0,6],[6,6,6,6,6,6,6,6,6,6,6]]

    def get(self):
      if(self.validation(2, 2, 2)):
        print "ok"
      else:
        print "ko"

    def other_color(self, color):
      if(color == 2):
        return 4
      else:
        return 2

    def check_valid_position(self, x, y):
      if(x>0 and x<10 and y>0 and y<10):
        return 1
      else:
        return 0

    def check_free_position(self, x, y):
      if(self.board[x][y] == 0 or self.board[x][y] == 1):
        return 1
      else:
        return 0

    def position_freedom(self, x, y):
      north = self.board[x][y-1]
      south = self.board[x][y+1]
      east = self.board[x+1][y]
      west = self.board[x-1][y]

      if(north == 0 or north == 1 or south == 0 or south == 1 or east == 0 or east == 1 or west == 0 or west == 1):
        return 1
      else:
        return 0

    def validation(self, color, x, y):
      self.check_valid_position(x, y)
      self.check_free_position(x, y)
      self.board[x][y] = color
      if(self.valid_move(color, x, y)):
        return 1
      else:
        return 0

    def chain_freedom(self, color, x, y):
      print "chain_freedom", color, x, y
      stack = deque([])
      if(self.position_freedom(x, y)):
        return 1
      else:
        north = self.board[x][y-1]
        south = self.board[x][y+1]
        east = self.board[x+1][y]
        west = self.board[x-1][y]
        if(north == color or north == color+1):
          stack.append(y-1)
          stack.append(x)
        if(south == color or south == color+1):
          stack.append(y+1)
          stack.append(x)
        if(east == color or east == color+1):
          stack.append(y)
          stack.append(x+1)
        if(west == color or west == color+1):
          stack.append(y)
          stack.append(x-1) 

        while(len(stack) > 0):
          x_tmp = stack.pop()
          y_tmp = stack.pop()
          if(self.position_freedom(x_tmp, y_tmp)):
            return 1
          else:
            self.board[x_tmp][y_tmp] = self.board[x_tmp][y_tmp] + 1
            north = self.board[x_tmp][y_tmp-1]
            south = self.board[x_tmp][y_tmp+1]
            east = self.board[x_tmp+1][y_tmp]
            west = self.board[x_tmp-1][y_tmp]
            if(north == color):
              stack.append(y_tmp-1)
              stack.append(x_tmp)
            if(south == color):
              stack.append(y_tmp+1)
              stack.append(x_tmp)
            if(east == color):
              stack.append(y_tmp)
              stack.append(x_tmp+1)
            if(west == color):
              stack.append(y_tmp)
              stack.append(x_tmp-1)
      return 0
          
    def valid_move(self, color, x, y):
      print "valid_move", color, x, y
      flag_capture = 0
      north = self.board[x][y-1]
      south = self.board[x][y+1]
      east = self.board[x+1][y]
      west = self.board[x-1][y]
      enemy_color = self.other_color(color)
      if(north == enemy_color):
        if(not self.chain_freedom(enemy_color, x, y-1)):
          self.capture(enemy_color, x, y-1)
          flag_capture = 1
      if(south == enemy_color):
        if(not self.chain_freedom(enemy_color, x, y+1)):
          self.capture(enemy_color, x, y+1)
          flag_capture = 1
      if(east == enemy_color):
        if(not self.chain_freedom(enemy_color, x+1, y)):
          self.capture(enemy_color, x+1, y)
          flag_capture = 1
      if(west == enemy_color):
        if(not self.chain_freedom(enemy_color, x-1, y)):
          self.capture(enemy_color, x-1, y)
          flag_capture = 1
      if(flag_capture):
        return 1
      else:
        if(self.position_freedom(x, y)):
          return 1
        else:
          if(north == color):
            if(self.chain_freedom(color, x, y-1)):
              return 1
          if(south == color):
            if(self.chain_freedom(color, x, y+1)):
              return 1
          if(east == color):
            if(self.chain_freedom(color, x+1, y)):
              return 1
          if(west == color):
            if(self.chain_freedom(color, x-1, y)):
              return 1
      return 0
        

    def uncheck_board(self):
      for i in range(10):
        for j in range(10):
          if(not (self.board[i][j] % 2)):
            self.board[i][j] = self.board[i][j] - 1
      return self.board

    def capture(self, color, x, y):
      print "capture",color, x, y
      stack = deque([])
      north = self.board[x][y-1]
      south = self.board[x][y+1]
      east = self.board[x+1][y]
      west = self.board[x-1][y]
      if(north == color or north == color+1):
        stack.append(y-1)
        stack.append(x)
      if(south == color or south == color+1):
        stack.append(y+1)
        stack.append(x)
      if(east == color or east == color+1):
        stack.append(y)
        stack.append(x+1)
      if(west == color or west == color+1):
        stack.append(y)
        stack.append(x-1)
      while(len(stack) > 0):
        x_tmp = stack.pop()
        y_tmp = stack.pop()
        self.board[x_tmp][y_tmp] = 0

        north = self.board[x_tmp][y_tmp-1]
        south = self.board[x_tmp][y_tmp+1]
        east = self.board[x_tmp+1][y_tmp]
        west = self.board[x_tmp-1][y_tmp]
        if(north == color or north == color+1):
          stack.append(y_tmp-1)
          stack.append(x_tmp)
        if(south == color or south == color+1):
          stack.append(y_tmp+1)
          stack.append(x_tmp)
        if(east == color or east == color+1):
          stack.append(y_tmp)
          stack.append(x_tmp+1)
        if(west == color or west == color+1):
          stack.append(y_tmp)
          stack.append(x_tmp-1) 
      print self.board
      return self.board


